<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /*
                        思路：
                        ①确定dp[i]即下标含义：dp[i]表示  i个节点组成的二叉搜索树的个数  i表示i个节点
                          如果整数1 ~ n中的 k 作为根节点值，则 1 ~ k-1 会去构建左子树，k+1 ~ n 会去构建右子树。
                            左子树出来的形态有 aaa 种，右子树出来的形态有 bbb 种，则整个树的形态有 a∗ba * ba∗b 种。
                            以 kkk 为根节点的 BSTBSTBST 种类数 = 左子树 BSTBSTBST 种类数 * 右子树 BSTBSTBST 种类数
                            就好比，左手有编号1/2/3的手环，右手有编号5/6/7的手环，那搭配就有9种

                        所以n个节点构造二叉树，左子树用掉j个，根节点用掉1个，右子树只能用i-j-1

                        假如i==3 那么dp[3]=以1为根节点+以2为根节点+以3为根节点构造的二叉搜索树的数量和

                        ②确定状态转移方程
                        dp[i]+=dp[j]*dp[i-j-1]
                        ③初始化dp
                        dp[1]=1
                        dp[0]=1 因为没有节点也代表二叉搜索树为空的情况 

                        */
            var numTrees = function (n) {
                let dp = new Array(n + 1).fill(0)
                dp[0] = 1
                dp[1] = 1
                for (let i = 2; i <= n; i++) {
                    for (let j = 0; j < i; j++) {
                        dp[i] += dp[j] * dp[i - j - 1]
                    }
                }

                return dp[n]
            }

            numTrees(3)
        </script>
    </body>
</html>
